package com.hle.sort.cmp;

import java.util.Iterator;

import com.hle.sort.Sort;
import com.hle.tools.Integers;

public class HeapSort<T extends Comparable<T>> extends Sort<T> {
	
	private int heapSize;
	
	@Override
	protected void sort() {
		heapSize = array.length;
		for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
			siftDown(i);
		}
		while (heapSize > 1) {
			swap(0, --heapSize);
			siftDown(0);
		}
	}
	
	private void siftDown(int index) {
		T element = array[index];
		int half = heapSize >> 1;
		while (index < half) {
			int child = (index << 1) + 1;
			T childElement = array[child];
			int rightChild = child + 1;
			if (rightChild < heapSize) {
				if (cmp(array[rightChild], childElement) > 0) {
					childElement = array[rightChild]; 
					child = rightChild;
				}
			}
			if (cmp(childElement, element) <= 0) break;
			array[index] = childElement;
			index = child;
		}
		array[index] = element;
	}
}
